package datastructure.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-26
 */
public class BinarySearch {
    private static int count = 0;

    public static void main(String[] args) {
        int[] array = {1, 7, 8, 8,55, 99};
        int index = binarySearch(array, 0, array.length - 1, 99);
        if (index == -1) {
            System.out.println("没查找到~~~~");
        } else {
            System.out.println("找到，下标为：" + index);
        }

        System.out.println();
        List<Integer> searchList = binarySearchList(array, 0, array.length - 1, 8);
        System.out.println(searchList);
    }

    /**
     * 二分查找
     * 查找数组需要有序
     *
     * @param array   查找数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 需要查找的值
     * @return 下标
     */
    private static int binarySearch(int[] array, int left, int right, int findVal) {

        System.out.println("二分次数："+ ++count);
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        if (findVal > array[mid]) {
            return binarySearch(array, mid + 1, right, findVal);
        } else if (findVal < array[mid]) {
            return binarySearch(array, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }


    /**
     * 二分查找
     * 查找数组需要有序
     *
     * @param array   查找数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 需要查找的值
     * @return 下标
     */
    private static List<Integer> binarySearchList(int[] array, int left, int right, int findVal) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        if (findVal > array[mid]) {
            return binarySearchList(array, mid + 1, right, findVal);
        } else if (findVal < array[mid]) {
            return binarySearchList(array, left, mid - 1, findVal);
        } else {
           List<Integer> resIndexList = new ArrayList<>();
            resIndexList.add(mid);
           // 向mid索引值的左边扫描
           int temp = mid-1;
           while (temp >= 0 && array[temp] == findVal){
               resIndexList.add(temp);
               temp--;
           }
           // 向mid索引右边扫描
            temp = mid+1;
            while (temp < array.length && array[temp] == findVal){
                resIndexList.add(temp);
                temp++;
            }
            return resIndexList;
        }
    }


}
